﻿public class Solution
{
    private IList<IList<string>> result = new List<IList<string>>();
    private IList<string> subString = new List<string>();
    public IList<IList<string>> Partition(string s)
    {
        trackbacking(s, 0);
        return result;
    }

    private void trackbacking(string s, int startIndex)
    {
        if (startIndex >= s.Length)
        {
            result.Add(new List<string>(subString));
            return;
        }
        for (int i = startIndex; i < s.Length; i++)
        {
            if (IsPalindrome(s, startIndex, i))
            {
                subString.Add(s[startIndex..(i+1)]);
                trackbacking(s, i + 1);
                subString.RemoveAt(subString.Count-1);
            }
        }
    }

    private bool IsPalindrome(string s, int startIndex, int i)
    {
        while (startIndex < i)
        {
            if (s[startIndex] != s[i]) return false;
            startIndex++;
            i--;
        }

        return true;
    }

    public static void Main(string[] args)
    {
        string s = "aab";

        Solution solution = new Solution();
        IList<IList<string>> result = solution.Partition(s);

        foreach (IList<string> res in result)
        {
            foreach (string r in res)
            {
                Console.Write($"{r} ");
            }
            Console.WriteLine();
        }
    }
}